//
//  treeImp.c
//  Chapter_1
//
//  Created by hao on 18/3/26.
//  Copyright © 2018年 hao. All rights reserved.
//

#include "treeImp.h"
#include <string.h>

int searchCharInOrder(char *order, char retch);

// 创建一个树的节点
Tree createTreeNode()
{
    Tree tree = malloc(sizeof(struct TreeNode));
    tree->left = TPL_LIST_NULL;
    tree->right = TPL_LIST_NULL;
    return tree;
}

// 根据前序和中序创建一颗树
// 前序 ABDFECGHI  根左右
// 中序 DBEFAGHCI  左根右
// 后序 DEFBHGICA  左右根
Tree createTreeOnPreMidOrder(char *preOrder, char *midOrder)
{
    Tree root;
    char first = *preOrder;
    // 获取序列的长度
    int preOrderLen = (int)strlen(preOrder);
    int midOrderLen = (int)strlen(midOrder);
    // 两个序列不相等return
    if (preOrderLen != midOrderLen) {
        return TPL_LIST_NULL;
    }
    
    if (preOrderLen == 0 && midOrderLen == 0) {
        return TPL_LIST_NULL;
    }
    //    printf("pre = %s, len = %d, mid = %s, len = %d \n", preOrder, preOrderLen, midOrder, midOrderLen);
    printf("preOrder = %s, midOrder = %s \n", preOrder, midOrder);
    // 根据前序根结点查找中序有没有该值，没有就return
    int midIndex = searchCharInOrder(midOrder, first);
    // 找不到分两种情况，第一种：最后一层结点的情况，只有一个右儿子或左儿子时
    // 第二种：确实找不到
    if (midIndex == TPL_NOT_FOUND && preOrderLen == 0 && midOrderLen == 0) {
        return TPL_LIST_NULL;
    }
    root = createTreeNode();
    root->charData = first;

    // 表示只有一个结点数据, 直接返回
    if (preOrderLen == 1) {
        char mid = *midOrder;
        if (first != mid) {
            Tree child = createTreeNode();
            child->charData = mid;
            root->left = child;
        }
        return root;
    }
    // 当长度等于2的时候，有同序和不同序，表示不同的结果
    //*midOrder+1: 指向*midOrder的结果再加1
    //*(midOrder+1): 指针指向midOrder首地址的下一地址
    if (preOrderLen == 2) {
        Tree child = createTreeNode();
        // 前序中序相等
        if (memcmp(preOrder, midOrder, 2) == 0) {
            child->charData = *(midOrder+1);
            root->right = child;
        } else {
            child->charData = *midOrder;
            root->left = child;
        }
        return root;
    }
    
    // 前序中序确定左右子树的数据有多少
    int leftSubCount = midIndex;
    int rightSubCount = midOrderLen-midIndex;
    // 前序的左子树所有数据
    //    char preLeftSubTree[leftSubCount];
    char *preLeftSubTree = malloc(sizeof(char)*leftSubCount);
    strncpy(preLeftSubTree, preOrder+1, leftSubCount);
    // 前序的右子树所有数据
    //    char preRightSubTree[rightSubCount];
    char *preRightSubTree = malloc(sizeof(char)*rightSubCount);
    strncpy(preRightSubTree, preOrder+1+midIndex, rightSubCount);
    // 中序序列的左子树所有数据
    //    char midLeftSubTree[leftSubCount];
    char *midLeftSubTree = malloc(sizeof(char)*leftSubCount);
    strncpy(midLeftSubTree, midOrder, leftSubCount);
    // 中序序列的右子树所有数据
    //    char midRightSubTree[rightSubCount];
    char *midRightSubTree = malloc(sizeof(char)*rightSubCount);
    // midOrder+midIndex+1 指针移动的位置，相当于从哪开始截取
    strncpy(midRightSubTree, midOrder+midIndex+1, rightSubCount);
    
    Tree leftTree = createTreeOnPreMidOrder(preLeftSubTree, midLeftSubTree);
    Tree rightTree = createTreeOnPreMidOrder(preRightSubTree, midRightSubTree);
    root->left = leftTree;
    root->right = rightTree;
    free(preLeftSubTree);
    free(preRightSubTree);
    free(midLeftSubTree);
    free(midRightSubTree);
    return root;
}

// 根据中序和后序创建一颗树
// 中序 DBEFAGHCI  左根右
// 后序 DEFBHGICA  左右根
Tree createTreeOnMidAndSuffixOrder(char *midOrder, char *sufOrder)
{
    Tree root;
    // 获取序列的长度
    int midOrderLen = (int)strlen(midOrder);
    int sufOrderLen = (int)strlen(sufOrder);
    char first = *(sufOrder+sufOrderLen-1);
    printf("first = %c \n", first);
    // 两个序列不相等return
    if (sufOrderLen != midOrderLen) {
        return TPL_LIST_NULL;
    }
    
    if (sufOrderLen == 0 && midOrderLen == 0) {
        return TPL_LIST_NULL;
    }
    // 根据前序根结点查找中序有没有该值，没有就return
    int midIndex = searchCharInOrder(midOrder, first);
    // 找不到分两种情况，第一种：最后一层结点的情况，只有一个右儿子或左儿子时
    // 第二种：找不到且长度为0，直接return
    if (midIndex == TPL_NOT_FOUND && sufOrderLen == 0 && midOrderLen == 0) {
        return TPL_LIST_NULL;
    }
    root = createTreeNode();
    root->charData = first;
    
    // 表示只有一个结点数据, 直接返回
    if (sufOrderLen == 1) {
        char mid = *midOrder;
        if (first != mid) {
            Tree child = createTreeNode();
            child->charData = mid;
            root->left = child;
        }
        return root;
    }
    // 当长度等于2的时候，有同序和不同序，表示不同的结果
    //*midOrder+1: 指向*midOrder的结果再加1
    //*(midOrder+1): 指针指向midOrder首地址的下一地址
    if (sufOrderLen == 2) {
        Tree child = createTreeNode();
        // 前序中序相等
        if (memcmp(sufOrder, midOrder, 2) == 0) {
            child->charData = *midOrder;
            root->left = child;
        } else {
            child->charData = *(midOrder+1);
            root->right = child;
        }
        return root;
    }
    
    // 中序后序确定左右子树的数据有多少
    int leftSubCount = midIndex;
    int rightSubCount = midOrderLen-midIndex-1;
    // 后序的左子树所有数据
    char *sufLeftSubTree = malloc(sizeof(char)*leftSubCount);
    strncpy(sufLeftSubTree, sufOrder, leftSubCount);
    // 后序的右子树所有数据
    char *sufRightSubTree = malloc(sizeof(char)*rightSubCount);
    strncpy(sufRightSubTree, sufOrder+midIndex, rightSubCount);
    // 中序序列的左子树所有数据
    char *midLeftSubTree = malloc(sizeof(char)*leftSubCount);
    strncpy(midLeftSubTree, midOrder, leftSubCount);
    // 中序序列的右子树所有数据
    char *midRightSubTree = malloc(sizeof(char)*rightSubCount);
    // midOrder+midIndex+1 指针移动的位置，相当于从哪开始截取
    strncpy(midRightSubTree, midOrder+midIndex+1, rightSubCount);
//    printf("sufLeftSubTree = %s, midLeftSubTree = %s \n", sufLeftSubTree, midLeftSubTree);
//    printf("sufRightSubTree = %s, midRightSubTree = %s \n", sufRightSubTree, midRightSubTree);
//    printf("\n");
    Tree leftTree = createTreeOnMidAndSuffixOrder(midLeftSubTree, sufLeftSubTree);
    Tree rightTree = createTreeOnMidAndSuffixOrder(midRightSubTree, sufRightSubTree);
    root->left = leftTree;
    root->right = rightTree;
    free(sufLeftSubTree);
    free(sufRightSubTree);
    free(midLeftSubTree);
    free(midRightSubTree);
    return root;
}

// 检索字符retch在order字符数组的位置
int searchCharInOrder(char *order, char retch)
{
    int slen = (int)strlen(order);
    for (int i = 0; i < slen; i++) {
        if (order[i] == retch) {
            return i;
        }
    }
    return TPL_NOT_FOUND;
}

// 递归遍历
void ergodicTree(Tree tree)
{
    if (tree != TPL_LIST_NULL) {
        printf("%c", tree->charData);
        ergodicTree(tree->left);
        ergodicTree(tree->right);
    }
}



